package com.leetcode.oj.medium.maximum_subarray;

/**
 * Find the contiguous subarray within an array (containing at least one number)
 * which has the largest sum.
 * 
 * For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray
 * [4,−1,2,1] has the largest sum = 6.
 * 
 * click to show more practice.
 * 
 * More practice: If you have figured out the O(n) solution, try coding another
 * solution using the divide and conquer approach, which is more subtle.
 * 
 * @author Telis
 * 
 */
public class Solution {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		System.out.println(s.maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1,
				-5, 4 }));
		System.out.println(s.maxSubArray(new int[] { -2, -1 }));
	}

	public int maxSubArray(int[] A) {
		if (A.length < 2)
			return A[0];
		int max = A[0];
		int temp = 0;
		for (int i = 0; i < A.length; i++) {
			temp += A[i];
			if (temp > max) {
				max = temp;
			}
			if (temp < 0) {
				temp = 0;
			}
		}
		return max;
	}
}
